package com.lee.algorithm.sort.quick;

import static com.lee.algorithm.sort.SortUtil.print;
import static com.lee.algorithm.sort.SortUtil.swap;

/***
 * @description 荷兰国旗（三区域划分）
 * @author 青石路
 * @date 2022/3/13 20:42
 */
public class ThreeRange {

    public static void main(String[] args) {
        int[] arr = new int[]{9,8,4,2,3,4,4,5,2,6,4};
        //int[] split = split(arr, 4);
        splitPlus(arr, 4);
        print(arr);
    }

    /**
     * 荷兰国旗（三区域划分）
     *      小于放左边，等于放中间，大于放右边
     * @param arr
     * @param target
     * @author 博客园 @ 青石路
     * @return
     */
    public static int[] split(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return arr;
        }
        int[] newArr = new int[arr.length];
        // lt：小于区域索引下标，gt：大于区域索引下标
        int lt = 0, gt = arr.length - 1;

        for(int i=0; i<arr.length; i++) {
            if (arr[i] < target) {
                newArr[lt++] = arr[i];
            } else if (arr[i] > target) {
                newArr[gt--] = arr[i];
            }
        }

        // 处理中间相等的部分
        for(int i=lt; i<=gt; i++) {
            newArr[i] = target;
        }
        return newArr;
    }

    /**
     * 荷兰国旗（三区域划分）
     *      小于放左边，等于放中间，大于放右边
     * @param arr
     * @param target
     * @author 博客园 @ 青石路
     * @return
     */
    public static void splitPlus(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // lt：左边界索引，gt：右边界索引
        int lt = -1, gt = arr.length, i=0;

        while(i < gt) {
            if (arr[i] < target) {
                // arr[i] 和 lt 后一个元素进行交换， lt右移，i++
                swap(arr, ++lt, i++);
            } else if (arr[i] > target) {
                // arr[i] 和 gt 前一个元素进行交换， gt 左移，i 不动
                swap(arr, --gt, i);
            } else {
                // arr[i] 等于 target，i++
                i++;
            }
        }
    }
}
